package 插入排序;

import java.util.Arrays;

public class 希尔排序 {
    public static void shell(int[] arr,int gap) {
        for (int i = gap; i <arr.length ; i++) {

            int tmp=arr[i];
            int j=i-gap;
            for (; j >= 0 ; j-=gap) {
                if (arr[j]>tmp) {
                    arr[j+gap]=arr[j];//将 j下标 的元素往后放
                }else {
                    break;//终止for循环
                }
            }
            arr[j+gap]=tmp;
        }
    }

    public static void shellSort (int[] arr) {
        //处理gap，构造gap取值序列，仍是一个数学难题，但肯定的是gap最后一次取值要为1
        int gap=arr.length;

        while (gap>1) {
            gap=gap/3+1;   //+1 保证最后一个gap序列值为1，除3  5  ... 都可以
            shell(arr,gap);
        }
    }

    public static void main(String[] args) {
        int[]  arr={10,6,9,3,5};
        shellSort(arr);
        System.out.println(Arrays.toString(arr));

        System.out.println();
    }

}
